The present invention relates to the evaluation of signals, more particularly to the classification of signal attributes of a non-stationary time series signal wherein such classification involves derivation of features thereof.
Non-stationary signals are used in almost every field of science and technology, such as the medical field, geophysical field, automobile manufacturing and submarine silencing (to name but a few). Some examples of non-stationary signals include, but are not limited to, the following: heartbeat electrocardiograms, seismic recordings, automobile vibration, and submarine acoustic transients.
Non-stationary signals are characterized by attributes that vary in some manner with time. It is for this reason that the study and analysis of such signals must involve a process that incorporates time. The most commonly uses process is termed time-frequency analysis. In general, time-frequency analysis is based on the construction of a two-dimensional distribution in time and frequency. In 1966, Leon Cohen developed a unifying formulation for time-frequency distributions with the correct marginals; see L. Cohen, xe2x80x9cGeneralized Phase-Space Distribution Functions,xe2x80x9d J. Math. Phys., vol. 7, no. 5, pp 781-786, 1966, incorporated herein by reference. Cohen""s generalized formulation stipulates that all time-frequency representations can be obtained from                               Q          ⁡                      (                          t              ,              f                        )                          =                              1                          2              ⁢                              xe2x80x83                            ⁢              π                                ⁢                      ∫                          ∫                              ∫                                                      {                                                                                            s                          *                                                ⁡                                                  (                                                      u                            -                                                                                          1                                2                                                            ⁢                              τ                                                                                )                                                                    ⁢                                              xe2x80x83                                            ⁢                      s                      ⁢                                              xe2x80x83                                            ⁢                                              (                                                  u                          +                                                                                    1                              2                                                        ⁢                            τ                                                                          )                                            ⁢                                              φ                        ⁡                                                  (                                                      θ                            ,                            τ                                                    )                                                                    ⁢                                              ⅇ                                                                                                            -                              j                                                        ⁢                                                          xe2x80x83                                                        ⁢                            θ                            ⁢                                                          xe2x80x83                                                        ⁢                            t                                                    -                                                      j                            ⁢                                                          xe2x80x83                                                        ⁢                            τ                            ⁢                                                          xe2x80x83                                                        ⁢                            2                            ⁢                            π                            ⁢                                                          xe2x80x83                                                        ⁢                            f                                                    +                                                      jθ                            ⁢                                                          xe2x80x83                                                        ⁢                            u                                                                                                                }                                    ⁢                                      ⅆ                    u                                    ⁢                                      ⅆ                                          xe2x80x83                                        ⁢                    τ                                    ⁢                                      ⅆ                                          xe2x80x83                                        ⁢                    θ                                                                                                          (        1        )            
where xcfx86(xcex8, xcfx84) is a two dimensional function, called the kernel, which determines the distribution and its properties. Ideally, such a distribution should be manifestly positive, for a proper interpretation as a joint time-frequency energy density function, and further, should yield the correct marginal densities of time, |s(t)|2, and frequency, |S(f)|2.
Mathematically, for a time-frequency distribution to be interpreted as a joint time-frequency energy density, it must satisfy the two fundamental properties of nonnegativity and the correct frequency and time marginals:                               Q          ⁡                      (                          t              ,              f                        )                          ≥        0                            (        2        )                                                      ∫                          -              ∞                        ∞                    ⁢                                    Q              ⁡                              (                                  t                  ,                  f                                )                                      ⁢                          xe2x80x83                        ⁢                          ⅆ              t                                      =                              "LeftBracketingBar"                          S              ⁡                              (                f                )                                      "RightBracketingBar"                    2                                    (                  3          ⁢          a                )                                                      ∫                          -              ∞                        ∞                    ⁢                                    Q              ⁡                              (                                  t                  ,                  f                                )                                      ⁢                          xe2x80x83                        ⁢                          ⅆ              f                                      =                              "LeftBracketingBar"                          s              ⁡                              (                t                )                                      "RightBracketingBar"                    2                                    (                  3          ⁢          b                )            
where       S    ⁡          (      f      )        =            ∫              -        ∞            ∞        ⁢                  s        ⁡                  (          t          )                    ⁢              ⅇ                              -            j2π                    ⁢                      xe2x80x83                    ⁢          f          ⁢                      xe2x80x83                    ⁢          t                    ⁢              ⅆ        t            
is the Fourier transform of the signal. Integrating the expression of (1) with respect to frequency yields the instantaneous power, |s(t)|2, provided xcfx86(xcex8, 0)=1. Likewise, integrating (1) with respect to time yields the energy density spectrum, |S(f)|2, provided xcfx86(0, xcfx84)=1. When a time-frequency distribution meets the conditions of (2) and (3) it is termed a xe2x80x9cpositive time-frequency distributionxe2x80x9d.
As it turned out, even though the generalized formulation for all time-frequency distributions was specified as early as 1966, the condition for positivity was not known until several years later when Cohen and Posch, and also Cohen and Zaparovanny, gave the condition and a simple, general formulation for positive time-frequency distributions. See L. Cohen and T. Posch, xe2x80x9cPositive Time-Frequency Distribution Functions,xe2x80x9d IEEE Trans. Acoust. Speech Signal Processing vol. ASSP-33, no. 1, pp 31-38, 1985, incorporated herein by reference; and, L. Cohen and Y. Zaparovanny, xe2x80x9cPositive Quantum Joint Distributions,xe2x80x9d J. Math. Phys., vol. 21, no. 4, pp 794-796, 1980, incorporated herein by reference. Thus, in 1985, it was known that positive time-frequency distributions could be constructed. However, it remained a secret of how to actually construct them for almost a decade.
It was not until 1994 that a means of constructing a positive time-frequency distribution using minimum cross-entropy was developed by Loughlin et al; see P. Loughlin, J. Pitton and L. Atlas, xe2x80x9cConstruction of Positive Time Frequency Distributions,xe2x80x9d IEEE Trans. Sig. Proc., vol. 42, no. 10, pp 2697-2705, 1994, incorporated herein by reference. The method of Loughlin et al. was certainly a theoretical breakthrough in science; however, the usefulness of the original formulation was limited because of computational constraints. These constraints were alleviated by Groutage; see Dale Groutage, xe2x80x9cA Fast Algorithm for Computing Minimum Cross-Entropy Positive Time-Frequency Distributions,xe2x80x9d IEEE Trans. Sig. Proc., vol. 45, no. 8, August 1997, pp 1954-1970, incorporated herein by reference.
The positive time-frequency distribution is currently the only way known to quantify the energy density of a non-stationary signalxe2x80x94in particular, to obtain a plausible representation of the energy density with the correct marginals.
Once a two-dimensional time-frequency distribution has been constructed, it is natural from a mathematical viewpoint to construct the statistical moments. These moments can be useful for formulating features that associate with the non-stationary signal s(t). For a signal s(t), the temporal and spectral moments are given by                               ⟨                      t            n                    ⟩                =                                            ∫                              -                ∞                            ∞                        ⁢                                          t                n                            ⁢                                                "LeftBracketingBar"                                      s                    ⁡                                          (                      t                      )                                                        "RightBracketingBar"                                2                            ⁢                              ⅆ                t                            ⁢                                                xe2x80x83                                ⁢                                  xe2x80x83                                            ⁢              and              ⁢                                                xe2x80x83                                ⁢                                  xe2x80x83                                            ⁢                              ⟨                                  f                  m                                ⟩                                              =                                    ∫                              -                ∞                            ∞                        ⁢                                          f                m                            ⁢                                                "LeftBracketingBar"                                      S                    ⁡                                          (                      f                      )                                                        "RightBracketingBar"                                2                            ⁢                              ⅆ                f                                                                        (        4        )            
where (n,m=1,2,3, . . . ) respectively. The joint time-frequency moments are given by                                           ⟨                                          t                n                            ⁢                              f                m                                      ⟩                    =                                    ∫                              -                ∞                            ∞                        ⁢                                          ∫                                  -                  ∞                                ∞                            ⁢                                                t                  n                                ⁢                                  f                  m                                ⁢                                  Q                  ⁡                                      (                                          t                      ,                      f                                        )                                                  ⁢                                  xe2x80x83                                ⁢                                  ⅆ                  t                                ⁢                                  ⅆ                  f                                ⁢                                                      xe2x80x83                                    ⁢                                      xe2x80x83                                                  ⁢                for                ⁢                                  xe2x80x83                                ⁢                n                                                    ,                  m          =          1                ,        2        ,        3        ,        …                            (        5        )            
Currently there are numerous methodologies for deriving features from time series records and imagery, but none of these are entirely satisfactory. These methods use a variety of mathematical approaches to derive the features including the joint moments of equation (5). A desirable method would be an approach that derived features, which associate with temporal and spectral moments analogous to those of equation (4). Most of the methods are xe2x80x9cad hocxe2x80x9d and use a so-called xe2x80x9creceiptxe2x80x9d that searches for salient aspects of the time series record or image. These techniques are rather limited in scope, and search for a priori features, which are thought to be contained within the time series record.
A known method which is not based on searching for a priori features is disclosed by L. M. D. Owsley et al; see L. M. D. Owsley, L. E. Atlas, and G. D. Bernard, xe2x80x9cSelf-Organizing Feature Maps and Hidden Markov Models for Machine-Tool Monitoring,xe2x80x9d IEEE Transactions on Signal Processing, vol. 45, no. 11, November 1997, pp 2787-2798, hereby incorporated herein by reference. Owsley et al. disclose the most current methodology not based upon a priori feature search, a methodology involving the so-called xe2x80x9cSelf Organizing Feature Map.xe2x80x9d
Essentially, according to Owsley et al., a xe2x80x9ccodebookxe2x80x9d is generated that contains vectors derived from a series of non-stationary signals from a given class of signals. The codebook contains an address for each vector. For the two-dimensional case, the address of each vector is its location in terms of the row-column that it resides. For example, a 5 by 5 codebook has 5 rows and 5 columns. Location (2,3) is for the vector residing at location occupied by the second row and third column. A test vector is compared to the vectors in the code book and the code book vector that matches the closest (via some technique such as the Euclidean Norm) is assigned the address associated with that vector in the code book. The feature for the test vector is the two-digit address.
Marinovic and Eichmann disclose a known method which is more closely associated with the presently inventive method than that which is disclosed by Owsley et al. See N. M. Marinovic and G. Eichmann, xe2x80x9cFeature Extraction and Pattern Classification in Space-Spatial Frequency Domain,xe2x80x9d Proc. SPIE, vol. 579, Conf. on Intelligent Robots and Computer Vision, Sep. 15-20, 1985, Cambridge, Mass., incorporated herein by reference; and, N. M. Marinovic and G. Eichmann, xe2x80x9cAn Expansion of Wigner Distribution and its Applications,xe2x80x9d Proceedings of the IEEE ICASSP-85, vol. 3, pp 1021-1024, 1985, incorporated herein by reference.
Leon Cohen references the work of Marinovic and Eichmann. See L. Cohen, Time-Frequency Analysis, Prentice-Hall, New York, 1995, incorporated herein by reference; see especially, pp 190-191, incorporated herein by reference. See also, L. Cohen, xe2x80x9cTime-Frequency Distributionsxe2x80x94A Review,xe2x80x9d Proceedings of the IEEE, vol. 77, no. 7, July 1989, pp 941-981, incorporated herein by reference. In particular, this method according to Marinovic and Eichmann uses Singular Value Decomposition (SVD) of the Wigner time-frequency distribution, and then suggests that the features are contained in the singular values.
Nevertheless, the method disclosed by Marinovic, Eichmann and Cohen has its shortcomings. Marinovic, Eichmann assigns import to the singular values. In reality, however, the singular values are pure numbers and do not contain pertinent information about the time series process. The truly pertinent information is contained in the singular vectors. However, the singular vectors are not proper density functions; thus, for the most part, the singular vectors are ignored by Marinovic, Eichmann, unrecognized by Marinovic, Eichmann as being a source of key features about the time series process.
Accordingly, there still exists a need, unfulfilled by current methodologies, to effectively derive features from a non-stationary time series signal, so that these features can be efficaciously utilized for classifying the attributes of the signal. In the medical field, for instance, the principal features could be used for non-intrusive diagnostics to detect malfunctions of internal organs. An example of such a malfunction would be the failure of a heart valve. The unique features derived from the recorded time series of the human heart could be used to classify the medial condition.
In view of the foregoing, it is an object of the present invention to provide method and apparatus for deriving features (especially, principal features) from a non-stationary time series signal, wherein such features can be used to classify the signal attributes.
The present invention provides a unique methodology for deriving, from a non-stationary time series signal, principal features, which can be used to classify the signal attributes. The new method of this invention inherently recognizes the value of the information contained within the singular vectors derived from the singular value decomposition (SVD) of a time-frequency distribution constructed from the associated time series. Accordingly, the inventive method alters the singular vectors such that they become proper density functions wherein principal features can be derived therefrom. Furthermore, by using this approach (since by construction, the SVD separates time and frequency), temporal and spectral moments can be used to derive features, as opposed to joint time and frequency moments.
The non-stationary signal feature extraction system according to this invention uses density functions derived from the singular value decomposition (SVD) of Cohen-Posch positive time-frequency distributions as well as other time-frequency distributions. According to frequent inventive practice, the time-frequency distributions are positive time-frequency distributions; nevertheless, according to this invention, the time-frequency distributions need not be positive time-frequency distributions.
In accordance with the present invention, the time-frequency distribution can be any time-frequency distribution which is obtainable from Cohen""s generalized formulation, wherein Cohen""s generalized formulation is given by the above-noted equation (1), viz.:       Q    ⁡          (              t        ,        f            )        =            1              2        ⁢                  xe2x80x83                ⁢        π              ⁢          ∫              ∫                  ∫                                    {                                                                    s                    *                                    ⁡                                      (                                          u                      -                                                                        1                          2                                                ⁢                        τ                                                              )                                                  ⁢                                  xe2x80x83                                ⁢                s                ⁢                                  xe2x80x83                                ⁢                                  (                                      u                    +                                                                  1                        2                                            ⁢                      τ                                                        )                                ⁢                                  φ                  ⁡                                      (                                          θ                      ,                      τ                                        )                                                  ⁢                                  ⅇ                                                                                    -                        j                                            ⁢                                              xe2x80x83                                            ⁢                      θ                      ⁢                                              xe2x80x83                                            ⁢                      t                                        -                                          j                      ⁢                                              xe2x80x83                                            ⁢                      τ                      ⁢                                              xe2x80x83                                            ⁢                      2                      ⁢                      π                      ⁢                                              xe2x80x83                                            ⁢                      f                                        +                                          jθ                      ⁢                                              xe2x80x83                                            ⁢                      u                                                                                  }                        ⁢                          ⅆ              u                        ⁢                          xe2x80x83                        ⁢                          ⅆ              τ                        ⁢                          xe2x80x83                        ⁢                                          ⅆ                θ                            .                                          
Generally speaking, according to the present invention, the density functions are derived from the singular value decomposition of time-frequency distributions. An emphasis of this invention is on the Cohen-Posch positive time-frequency distributions, which are preferably used for many embodiments of this invention. The positive time-frequency distribution is always manifestly positive and always yields the correct marginal densities of time and frequency. When the features are derived from singular value decomposition (SVD) of Cohen-Posch positive time-frequency distributions, the features associate with energy density highlights; this represents an advantage of inventively implementing a Cohen-Posch positive time-frequency distribution.
Nevertheless, the inventive methodology is not restricted to Cohen-Posch positive time-frequency distributions. Other time-frequency distributions (i.e., xe2x80x9cnon-positivexe2x80x9d time-frequency distributions), such as the spectrogram distribution or the Wigner distribution (to name but a couple), can also be used in accordance with the present invention. Utilization of a spectrogram, for instance, may be advantageous insofar as being speedier in application.
Any xe2x80x9cdiscrete timexe2x80x9d (as distinguished from xe2x80x9ccontinuous timexe2x80x9d) time-frequency distribution, by definition, will be susceptible to being expressed in mathematical matrix form, and hence will lend itself to inventive practice. In the light of this disclosure, the ordinarily skilled artisan will be capable of practicing this invention in association with any of a variety of time-frequency distribution genres.
An inventive method for deriving at least one feature from a non-stationary time series signal, typically wherein said at least one feature is suitable for classifying at least one attribute of the signal, comprises: based on the signal, generating a time-frequency distribution matrix; decomposing the time-frequency distribution matrix; performing an element-by-element square of singular vectors; sorting and truncating the non-principal singular values; obtaining density functions; normalizing the density functions; and, formulating at least one feature from the normalized density functions.
In accordance with typical embodiments of the present invention, a method for deriving features from a non-stationary time series signal comprises the following steps: generating a time-frequency distribution matrix, preferably a positive time-frequency distribution matrix (this step corresponding to what is termed herein xe2x80x9csub system number onexe2x80x9d); decomposing the positive time-frequency distribution matrix (this step corresponding to what is termed herein xe2x80x9csub system number twoxe2x80x9d); performing an element-by-element square of the singular vectors, thereby formulating the density functions (this step corresponding to what is termed herein xe2x80x9csub system number threexe2x80x9d); sorting and truncating all but the principal singular values (this step corresponding to what is termed herein xe2x80x9csub system number fourxe2x80x9d); weighting the element-by-element square of the singular vectors by the principal singular values (this step corresponding to what is termed herein xe2x80x9csub system number fivexe2x80x9d); normalizing the density functions formulated by the weighting of the element-by-element square of the singular vectors (this step corresponding to what is termed herein xe2x80x9csub system number sixxe2x80x9d); and, formulating features (e.g., moments or other quantities) from the normalized density functions (this step corresponding to what is termed herein xe2x80x9csub system number sevenxe2x80x9d).
The present invention can be efficaciously practiced in association with known computer technology.
Some embodiments of the present invention provide a machine having a memory. The machine contains a data representation of at least one feature derived from a non-stationary time series signal, typically wherein at least one feature is suitable for classifying at least one attribute of the signal. The data representation is generated, for availability for containment by the machine, by the method comprising: based on the signal generating a time-frequency distribution matrix (e.g., a positive time-frequency distribution matrix); decomposing the time-frequency distribution matrix; performing an element-by-element square of singular vectors; sorting and truncating the non-principal singular values; obtaining density functions; normalizing the density functions; and, formulating at least one feature from the normalized density functions.
Some embodiments of the present invention provide a memory for storing data for access by an application program being executed on a processing system. The memory comprising a data representation of at least one feature derived from a non-stationary time series signal, typically wherein at least one feature is suitable for classifying at least one attribute of said signal. The data representation is stored in the memory and includes information resident in a database used by the application program. The data representation is generated, for availability for storage in said memory, by the method comprising: based on the signal, generating a time-frequency distribution matrix (e.g., a positive time-frequency distribution matrix); decomposing the time-frequency distribution matrix; performing an element-by-element square of singular vectors; sorting and truncating the non-principal singular values; obtaining density functions; normalizing the density functions; and, formulating at least one feature from the normalized density functions.
Other objects, advantages and features of this invention will become apparent from the following detailed description of the invention when considered in conjunction with the accompanying drawings.
The following appendices are hereby made a part of this disclosure:
Attached hereto marked APPENDIX A and incorporated herein by reference is the following manuscript which discloses various aspects of the present invention: Dale Groutage and David Bennink, xe2x80x9cFeature Sets for Non-Stationary Signals Derived from Moments of the Singular value decomposition of Cohen-Posch (Positive Time-Frequency) Distributions,xe2x80x9d submitted (Mar. 16, 1998) to the IEEE Transactions on Signal Processing, accepted for publication. This manuscript includes a cover page, plus 34 pages of text, plus 23 sheets of drawings.